/**
 * 76. 最小覆盖子串
 * @param s 字符串
 * @param t 最小字串
 */
function minWindow(s: string, t: string): string {
  let left = 0
  let right = 0
  const need = new Map()
  for (let c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1)
  }
  let needType = need.size
  let res = ''
  while (right < s.length) {
    const c = s[right]
    if (need.has(c)) {
      need.set(c, need.get(c) - 1)
      if (need.get(c) === 0) {
        needType -= 1
      }
    }
    while (needType === 0) {
      const newRes = s.substring(left, right + 1)
      if (!res || newRes.length < res.length) {
        res = newRes
      }
      const c2 = s[left]
      if (need.has(c2)) {
        need.set(c2, need.get(c2) + 1)
        if (need.get(c2) === 1) {
          needType += 1
        }
      }
      left += 1
    }
    right += 1
  }
  return res
}